/**
 * 嵌套循环会超时
 */
function maxProfit(prices: number[]): number {
  // 只需要找到最大的前后差 而不需要确定到底是哪两个时机
  let max = 0
  for (let i = prices.length - 1; i >= 1; i--) {
    for (let j = i - 1; j >= 0; j--) {
      let diff = prices[i] - prices[j]
      max = Math.max(0, diff, max)
    }
  }
  return max
};

/**
 * 官方题解
 * 总是计算当前值 与前面的最小值算利润
 */
function maxProfit2(prices: number[]): number {
  let maxP = 0
  let min = Infinity
  prices.forEach(p => {
    maxP = Math.max(p - min, maxP)
    min = Math.min(p, min)
  })
  return maxP
};

module.exports.maxProfit = maxProfit2